Kruskal's Algorithm

• Step 1

  Find the cheapest edge in the graph (if there is more than one, pick one at random). Mark it with any given colour, say red.

• Step 2

  Find the cheapest unmarked (uncoloured) edge in the graph that doesn't close a coloured or red circuit. Mark this edge red.

• Step 3

  Repeat Step 2 until you reach out to every vertex of the graph (or you have N ; 1 coloured edges, where N is the number of Vertices.) The red edges form the desired minimum spanning tree.

  ---

  Prim's Algorithm

   

  • Step 0

    Pick any vertex as a starting vertex. (Call it S). Mark it with any given colour, say red.

  • Step 1

    Find the nearest neighbour of S (call it P₁). Mark both P₁ and the edge SP₁ red. cheapest unmarked (uncoloured) edge in the graph that doesn't close a coloured circuit. Mark this edge with same colour of Step 1.

  • Step 2

    Find the nearest uncoloured neighbour to the red subgraph (i.e., the closest vertex to any red vertex). Mark it and the edge connecting the vertex to the red subgraph in red.

  • Step 3

    Repeat Step 2 until all vertices are marked red. The red subgraph is a minimum spanning tree.

  ---

  Boruvka's algorithm

  (Actually Boruvka should be spelled with a small raised circle accent over the "u".) Although this seems a little complicated to explain, it's probably the easiest one for computer implementation since it doesn't require any complicated data structures. The idea is to do steps like Prim's algorithm, in parallel all over the graph at the same time.

      Boruvka's algorithm:
      make a list L of n trees, each a single vertex
      while (L has more than one tree)
          for each T in L, find the smallest edge connecting T to G-T
          add all those edges to the MST
          (causing pairs of trees in L to merge)
  

  As we saw in Prim's algorithm, each edge you add must be part of the MST, so it must be ok to add them all at once.

  Analysis: This is similar to merge sort. Each pass reduces the number of trees by a factor of two, so there are O(log n) passes. Each pass takes time O(m) (first figure out which tree each vertex is in, then for each edge test whether it connects two trees and is better than the ones seen before for the trees on either endpoint) so the total is O(m log n).

  ---

  A hybrid algorithm

  This isn't really a separate algorithm, but you can combine two of the classical algorithms and do better than either one alone. The idea is to do O(log log n) passes of Boruvka's algorithm, then switch to Prim's algorithm. Prim's algorithm then builds one large tree by connecting it with the small trees in the list L built by Boruvka's algorithm, keeping a heap which stores, for each tree in L, the best edge that can be used to connect it to the large tree. Alternately, you can think of collapsing the trees found by Boruvka's algorithm into "supervertices" and running Prim's algorithm on the resulting smaller graph. The point is that this reduces the number of remove min operations in the heap used by Prim's algorithm, to equal the number of trees left in L after Boruvka's algorithm, which is O(n / log n).

  Analysis: O(m log log n) for the first part, O(m + (n/log n) log n) = O(m + n) for the second, so O(m log log n) total.